package com.leetcode.蓝桥杯.十二届国赛;

import java.util.Arrays;

/**
对于─棵有根二叉树T，小蓝定义这棵树中结点的权值W(T)如下:
空子树的权值为0。
如果一个结点v有左子树L,右子树R，分别有C(L)和C(R)个结点，则W(v)=1＋2W(L)+3W(R)+(C(L))2C(R)
树的权值定义为树的根结点的权值。
小蓝想知道，对于—棵有2021个结点的二叉树，树的权值最小可能是多少?

 * @author LZF
 *
 */
public class 填空题4 {
	/**
	 * 解题思路：总的节点数为2021，那就计算左子树的节点数从0开始，到2020的权值，取最小值。
	 * 利用递归，无法解出，原因是，会重复计算。比如说，计算calculate(2021)，会计算到calculate(2020)和calculate(2000)，
	 * 而计算calculate(2020)的时候，也会计算calculate(2000),以此类推，会有非常多重复计算的，代价变大
	 * 
	 * 利用动态规划，根据递归的缺点，我们每计算完一个，利用数组保存，下次就直接取值，不用再重复计算
	 * 所以关键代码几乎是一样的
	 * @param args
	 */
	public static void main(String[] args) {
		System.out.println(2653631372L);
	}
	
	//递归，算不出！！
//	public static long calculate(int nodeNum) {
//		if(nodeNum == 0) return 0;
//		if(nodeNum == 1) return 1;
//		nodeNum--;
//		long sum = Long.MAX_VALUE;
//		for(int i = 0;i <= nodeNum;i++) {
//			long temp = 0;
//			temp = 2 * calculate(i) + 3 * calculate(nodeNum - i) + i * i * (nodeNum - i);
//			sum = Math.min(sum,temp);
//		}
//		return sum + 1;
//	}
	
	//动态规划
	public static long calculate(int nodeNum) {
		long[] dp = new long[nodeNum + 1];
		//数组全部置为最大值
        Arrays.fill(dp, Long.MAX_VALUE);
        //初始置为0
        dp[0] = 0;
        for(int i = 1; i <= 2021; i++){//总的节点数从1开始算起，算到2021
            for(int j = 0; j < i; j++){//j表示左子树的节点数
                //左边节点j个，右边节点i - 1 - j个
                dp[i] = Math.min(dp[i], 1 + 2 * dp[j] + 3 * dp[i - 1 - j] + j * j * (i - 1 - j));
            }
        }
        return dp[nodeNum];
	}
}
